﻿// 4246. 最短路径和.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>

/*
https://www.acwing.com/problem/content/4249/

给定一个 n
 个点 m
 条边的无重边无自环的有向图。

点的编号 1∼n
。

任意两点之间均可相互抵达。

请你计算，从点 1
 到其他所有点的最短路径长度以及从其他所有点到点 1
 的最短路径长度，并将这 2×(n−1)
 个最短路径长度相加后输出结果。

输入格式
第一行包含整数 T
，表示共有 T
 组测试数据。

每组数据第一行包含两个整数 n,m
。

接下来 m
 行，每行包含三个正整数 a,b,c
，表示从点 a
 到点 b
 存在一条边，长度为 c
。

输出格式
每组数据输出一行，一个整数表示结果。

数据范围
1≤T≤10
,
1≤n,m≤106
,
1≤a,b≤n
,
一组数据中所有的 c
 相加之和不超过 109
。

输入样例：
2
2 2
1 2 13
2 1 33
4 6
1 2 10
2 1 60
1 3 20
3 4 10
2 4 5
4 1 50
输出样例：
46
210
*/
int main()
{
    std::cout << "Hello World!\n";
}

 